#include "stdlib.h"
#include "assert.h"
#include "err.h"
#include "bool.h"
#include "union.h"

/* Estructura del TAD */
struct sunionfind{
	tufalpha* rep;
	int max_tam;		
	int componentes;
};

/* Constructor del TAD */
union_find uf_create(const size_t max){
	union_find uf;
	uf = (union_find)calloc(1,sizeof(struct sunionfind));
	if(uf != NULL){
		uf->componentes = 0;
		uf->max_tam = max;
		uf->rep = (tufalpha*)calloc(max,sizeof(tufalpha));
		if (uf->rep == NULL){
			free(uf);
			uf = NULL;
                        errx(EXIT_FAILURE,"No hay memoria disponible");
		}
	}
        else errx(EXIT_FAILURE,"No hay memoria disponible");
	return uf;
}

/* Agregar un elemento al Conjunto */
void uf_add_singulete(union_find uf,const tufalpha el){
	assert(uf != NULL);
	assert(el < uf->max_tam);
	if(uf->rep[el] == 0){
		uf->componentes = uf->componentes + 1;	
		uf->rep[el] = -1;
	}		
}

/* Determina la componenete conexa a la que pertenece el elemento en cuestión */
tufset uf_find(union_find uf, const tufalpha el){
	tufset r;
	tufalpha j, k;
	j = el;
	while (!is_rep(uf,j)){
		j = uf->rep[j];
	}
	r = j;
	j = el;
	while (!is_rep(uf,j)){
		k = uf->rep[j];
		uf->rep[j] = r;
		j = k;
	}
	return r;
}

/* Une los los conjuntos representados por s1 y s2 */
void uf_union(union_find uf, const tufset s1, const tufset s2){
	assert(uf != NULL);
	assert(s1 != s2);
	if (uf->rep[s1] >= uf->rep[s2]){
		uf->rep[s2] = uf->rep[s1] + uf->rep[s2];
		uf->rep[s1] = s2;
	} else {
		uf->rep[s1] = uf->rep[s2] + uf->rep[s1];
		uf->rep[s2] = s1;
	}
	uf->componentes = uf->componentes - 1;	
}

/* Determina si existe exactamente un conjunto de nodos */
Bool uf_oneset(const union_find uf) {
	assert(uf != NULL);
	return (uf->componentes == 1);
}

/* Retorna el número de componentes conexas */
int uf_cantset(union_find uf){
	assert(uf != NULL);
	return uf->componentes;
}

/* Destructor del TAD */
union_find uf_destroy(union_find uf){
	assert(uf !=  NULL);
	free(uf->rep);
        uf->rep = NULL;
	free(uf);
        uf = NULL;
	return uf;
}

/* Determina si el elemento j es representante de su clase */
Bool is_rep(union_find uf, tufalpha j){
	assert(uf != NULL);
        assert(0 <= j && j < uf->max_tam);
	return uf->rep[j] < 0;
}
